package com.my.test.string;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class NOccurenceFinder {
	
	/**
	 * For a string 'baccabcd', n=2, so 'b' is the first char which matches:
	 * occurrence = 2, postion 0 should be returned
	 * 
	 * @param str
	 * @param n
	 * @return
	 */
	public static int findFirstNOccurPos(String str, int n) {
		Map<Character, Integer> firstOccrMap = new HashMap<Character, Integer>();
		Map<Character, Integer> occurMap = new HashMap<Character, Integer>();
		Map<Character, Integer> nOccurMap = new HashMap<Character, Integer>();
		for(int i=0; i<str.length(); i++) {
			Character c = str.charAt(i);
			if(!firstOccrMap.containsKey(c)) {
				firstOccrMap.put(c, i);
			}
			Integer prevCnt = occurMap.get(c) != null ? occurMap.get(c) : 0;
			if(prevCnt == n) {
				occurMap.remove(c);
				nOccurMap.remove(c);
				continue;
			}
			if (prevCnt + 1 == n) {
				nOccurMap.put(c, n);
				occurMap.put(c, n);
			} else {
				occurMap.put(c, prevCnt+1);
			}
		}
		Set<Character> chs = nOccurMap.keySet();
		Iterator<Character> iter = chs.iterator();
		Character firstOccurChar = iter.next();
		while (iter.hasNext()) {
			Character cur = iter.next();
			if (firstOccrMap.get(cur) < firstOccurChar) {
				firstOccurChar = cur;
			}
		}
		return firstOccrMap.get(firstOccurChar);
	}

	public static void main(String[] args) {
		int n = 3;
		System.out.println("First occurrence " + n + " starts at: " + findFirstNOccurPos("baccabcd", n));
	}

}
